package leetcode.editor.cn.dsa03_stack;
//输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如，序列 {1,2,3,4,5} 是某栈
//的压栈序列，序列 {4,5,3,2,1} 是该压栈序列对应的一个弹出序列，但 {4,3,5,1,2} 就不可能是该压栈序列的弹出序列。 
//
// 
//
// 示例 1： 
//
// 输入：pushed = [1,2,3,4,5], popped = [4,5,3,2,1]
//输出：true
//解释：我们可以按以下顺序执行：
//push(1), push(2), push(3), push(4), pop() -> 4,
//push(5), pop() -> 5, pop() -> 3, pop() -> 2, pop() -> 1
// 
//
// 示例 2： 
//
// 输入：pushed = [1,2,3,4,5], popped = [4,3,5,1,2]
//输出：false
//解释：1 不能在 2 之前弹出。
// 
//
// 
//
// 提示： 
//
// 
// 0 <= pushed.length == popped.length <= 1000 
// 0 <= pushed[i], popped[i] < 1000 
// pushed 是 popped 的排列。 
// 
//
// 注意：本题与主站 946 题相同：https://leetcode-cn.com/problems/validate-stack-sequences/ 
// 👍 94 👎 0

public class ZhanDeYaRuDanChuXuLieLcofOffer31 {
    public static void main(String[] args) {
        System.out.println(2 << 2);
        Solution solution = new ZhanDeYaRuDanChuXuLieLcofOffer31().new Solution();
        int[] pushed = {1, 2, 3, 4, 5};
        int[] popped = {4, 5, 3, 2, 1};
        System.out.println(solution.validateStackSequences(pushed, popped));
        int[] popped2 = {4, 3, 5, 1, 2};
        System.out.println(solution.validateStackSequences(pushed, popped2));
        int[] pushed3 = {0, 2, 1};
        int[] popped3 = {0, 1, 2};
        System.out.println(solution.validateStackSequences(pushed3, popped3));
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public boolean validateStackSequences(int[] pushed, int[] popped) {
            //长度小于3不会存在错误情况
            if (pushed.length < 3) return true;
            //假设入栈序列pushed[1,2,3,4,5]，出栈序列poped[4,5,3,2,1]
            //使用辅助栈，遍历入栈数组，依次入栈
            //每次入栈后循环判断出栈数组的每一个元素是否等于当前栈的栈顶元素，等于则进行出栈操作
            //最终只要能遍历完出栈序列或者辅助栈为空就说明该出栈序列是正确的
            int popIndex = 0; //记录当前出栈索引
            //辅助栈，使用数组模拟
            int[] stack = new int[pushed.length];
            int index = -1; //记录栈顶元素
            for (int i = 0; i < pushed.length; i++) {
                stack[++index] = pushed[i]; //依次入栈
                while (index != -1 && popped[popIndex] == stack[index]) { //当前出栈元素等于栈顶元素
                    index--; //出栈操作
                    popIndex++; //索引指向下一个出栈元素
                }
            }
            // index == -1 || popIndex == popped.length说明全部出栈了
            return index == -1;
        }
        //leetcode submit region end(Prohibit modification and deletion)
    }
}
